//链表js实现方式：
// 1：单向链表：线性数据结构
// 2：双向链表
// 3：单向循环链表
// 4：双向循环链表
// 5：环形链表

/* 设计链表思路：两个类，一个用Node类表示节点；另一个是LinkedList类提供插入节点，删除节点等操作 */

/*节点:节点包含了两部分，一部分是存储数据的元素区域，一部分是指向下一个节点的指针区域，它们共同构成一个节点。*/
class Node {
    constructor(data) {
        this.data = data; //数据
        this.next = null; //指针
    }
}
/* 单向链表 */
class LinkedList {
    //如果未传递 “head” 节点，则它将初始化为 null
    constructor(head = null) {
        this.length = 0;
        this.head = head; //头节点
    }
    //是否是空链表
    isEmpty() {
        if (this.head === null) {
            return true;
        } else {
            return false;
        }
    }
    //查找节点：从头结点开始查找，如果没找到就把当前指针往后移，找到就返回该节点，如果遍历完没找到就直接返回null
    find(data) {
        let currentNode = this.head;
        while (currentNode && currentNode.data !== data) {
            currentNode = currentNode.next;
        }
        return currentNode;
    }
    //获取最后一个节点,只要当前节点的下一节点不为空，就一直向后遍历
    findLast() {
        let currentNode = this.head;
        //空链表
        if (currentNode === null) {
            return null;
        }
        while (currentNode.next) {
            currentNode = currentNode.next;
        }
        return currentNode;
    }
    //添加节点,直接在最后一个节点添加新的节点
    append(data) {
        //创建一个新的节点
        let newNode = new Node(data);
        let lastNode = this.findLast();
        //空链表
        if (lastNode === null) {
            this.head = newNode;
        } else {
            lastNode.next = newNode;
        }
        this.length++;
    }
    //删除节点
    remove(data) {
        if (!this.find(data)) {
            return console.log("没有该节点");
        }
        let currentNode = this.head;
        while (currentNode.data !== data) {
            currentNode = currentNode.next;
        }
        //考虑只有一个节点的情况
        this.length--;
        if (currentNode.next === null) {
            this.head = null;
        } else {
            currentNode.data = currentNode.next.data;
            currentNode.next = currentNode.next.next;
        }
    }
    //显示链表每个节点的数据
    list() {
        if (this.isEmpty()) {
            return console.log("该链表为空链表");
        } else {
            let currentNode = this.head;
            let result = '';
            while (currentNode) {
                result += currentNode.data;
                currentNode = currentNode.next;
                if (currentNode) {
                    result += '——>';
                }
            }
            console.log(result);
        }
    }
    //改变节点的数据
    update(oldDtata, newData) {
        try {
            this.find(oldDtata).data = newData;
        } catch (e) {
            console.log("没有该节点");
        }
    }
    //插入节点：在某节点后插入新的节点
    insert(nodeData, data) {
        try {
            let currentNode = this.find(nodeData);
            let newNode = new Node(data);
            newNode.next = currentNode.next;
            currentNode.next = newNode;
            this.length++;
        } catch (e) {
            console.log("没有该节点");
        }
    }
}
let list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.list();
list.update(3,4);
list.list();
list.remove(2);
list.list();